package leetcode;

import java.util.ArrayDeque;
import java.util.Queue;

public class LeetCode100 {
    private boolean result = true;

    public boolean isSameTree1(TreeNode p, TreeNode q) {
        judge(p, q);
        return result;
    }

    public void judge(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            if (p == q)
                return;
            else {
                result = false;
                return;
            }
        }
        if (p.val != q.val) {
            result = false;
            return;
        }
        judge(p.left, q.left);
        judge(p.right, q.right);
    }

    //层次遍历
    public boolean isSameTree2(TreeNode p, TreeNode q) {
        ArrayDeque<TreeNode> dict1 = new ArrayDeque<>();
        ArrayDeque<TreeNode> dict2 = new ArrayDeque<>();
        dict1.add(p);
        dict2.add(q);

        while (!dict1.isEmpty()) {
            p = dict1.removeFirst();
            q = dict2.removeFirst();

            if (!check(p, q)) return false;
            if (p != null) {
                // in Java nulls are not allowed in Deque
                if (!check(p.left, q.left)) return false;
                if (p.left != null) {
                    dict1.addLast(p.left);
                    dict2.addLast(q.left);
                }
                if (!check(p.right, q.right)) return false;
                if (p.right != null) {
                    dict1.addLast(p.right);
                    dict2.addLast(q.right);
                }
            }
        }
        return false;
    }

    public boolean check(TreeNode p, TreeNode q) {
        // p and q are null
        if (p == null && q == null) return true;
        // one of p and q is null
        if (q == null || p == null) return false;
        if (p.val != q.val) return false;
        return true;
    }
//------------------------------------------------------------------

    //改进版
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // p and q are both null
        if (p == null && q == null) return true;
        // one of p and q is null
        if (q == null || p == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.right, q.right) &&
                isSameTree(p.left, q.left);
    }
}
